package Ep06_BinaryTree.BT30_0450;

import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/9 15:25
 * 说明：
 *      分类讨论要删除的节点：
 *      1. 没有要删的
 *      2. 左右都为空（叶子节点）
 *      3. 左不空，右空
 *      4. 左空，右不空
 *      5. 左右都不空
 *      如果左右都不空，如何重构呢？
 *      把左子树放在右子树的最左下的节点处，或者把右子树放在左子树最右下的节点处
 */

public class Mine {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (key == root.val){
            // 这里涵盖了二者都为null（叶子节点）和其中仅有一个null（单边孩子，另一边为null的节点）的情况
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            TreeNode cur = root.right;
            while (cur.left != null) {    // 找右子树的最左下角的节点（大于当前root的最小的节点）
                cur = cur.left;
            }
//            root.val = cur.val;     // 不直接改变指向关系，而是把root改为cur
//            root.right = deleteNode(root.right, cur.val);   // 然后再把cur删了，cur必是叶子节点，所以可以直接删
            cur.left = root.left;   // 改变结构的写法，把root的左孩子交给cur，然后把root的右return给root的parent接住
            return root.right;
        } else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }
        return  root;
    }
}
